package _18_剑指OfferII;

public class _070_剑指OfferII排序数组中只出现一次的数字 {

    // 二分查找, 保证被二分出来的左右数据规模相同
    // 如果num[mid] = num[mid + 1], 说明出现的数在右边
    public int singleNonDuplicate(int[] nums) {
        int begin = 0;
        int end = nums.length - 1;
        while (begin < end) {
            int mid = begin + ((end - begin) >> 1);
            mid = mid % 2 == 1 ? mid - 1 : mid;
            if (nums[mid] == nums[mid + 1]) {
                begin = mid + 2;
            } else {
                end = mid;
            }
        }
        return nums[begin];
    }

    // 按位异或，最后剩下的数就是单独的数
    public int singleNonDuplicate1(int[] nums) {
        int n = 0;
        for (int num : nums) {
            n ^= num;
        }
        return n;
    }

}
